package leetCode.offer47;

/**
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 */
public class Solution1 implements Solution{

    /**
     * 解决此题的关键在于：
     * 定义坐标（row,col）处的最大价值为f(row,col)
     * 则分析可知： f(row,col) = max{f(row-1,col),f(row,col-1)} + grid[row,col]
     * 由此可以递推处每个坐标的最大价值，由此计算出目标坐标的最大价值
     * @param grid 二位数组
     * @return
     */
    @Override
    public int maxValue(int[][] grid) {
        int[][] maxValues = new int[grid.length][grid[0].length];
        for(int row = 0;row<maxValues.length;row++) {
            int upValue = 0;
            int leftValue = 0;
            for(int col = 0;col<grid[0].length;col++){
                if(row-1>=0){
                    upValue = maxValues[row-1][col];
                }
                if(col-1>=0){
                    leftValue = maxValues[row][col-1];
                }
                if(upValue>leftValue){
                    maxValues[row][col] = upValue + grid[row][col];
                }else{
                    maxValues[row][col] = leftValue + grid[row][col];
                }
            }
        }
        return maxValues[grid.length-1][grid[0].length-1];
    }

    public static void main(String[] args) {
        int[][] param = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(new Solution1().maxValue(param));
    }

}
